#include "headfiles.h"

using namespace std;

// Two scenarios for the in-order next node
// 1. If the node has a right child, the most left child of the right
//    child is the next order
// 2. If the node does not have a right child, then if it is a 
//    left child of some node, or any of its parent or parent's parent 
//    is left child, then the parentof the left child is the next node;
//    Otherwise, it is the last child, and its next node is NULL

NODE * findNextNode(NODE *n) {
	if (n == NULL) {
		return NULL;
	}

	NODE *next = n->right;
	// has a right child
	if (next) {
		while (next->left) {
			next = next->left;
		}

		return next;
	}
	// does not have a right child
	else {
		NODE *p = n->p;
		while (p) {
			if (p->left == n) {
				return p;
			}
			else {
				n = p;
				p = n->p;
			}
		}
		
		return NULL;
	}

	return NULL;
}

NODE *findPreviousNode(NODE *n) {
	if (n == NULL) {
		return NULL;
	}

	// if it has a left child, then the left child's 
	// rightmost child is its previous node
	NODE *child = n->left;
	if (child) {
		while (child->right) {
			child = child->right;
		}
		return child;
	}
	else {
		NODE *p = n->p;
		while (p) {
			if (p->right == n) {
				return p;
			}
			else {
				n = p;
				p = n->p;
			}
		}

		return NULL;
	}
	
	return NULL;
}
